1. Field of the Invention
This invention relates to the partitioning of three-dimensional parts such as mechanical, optical or biological parts into simpler representations to support downstream solid modeling applications that perform combinatorial surface operations on the geometric representations of the series of sub-parts to analyze physical characteristics such as radiation, mechanical, optical, thermal, structural or biological of the original part.
2. Description of the Related Art
Many modern computer-aided processes must subdivide space in and surrounding a solid geometry of a part of interest such as a mechanical, optical or biological part to perform their computations. Such subdivision is a necessary cost of doing business, but can become computationally prohibitively expensive when the geometry becomes even moderately complex. One example of this is radiation transport computation. To model what happens when radiation impinges on a part, the transport application must consider both bounding surfaces (how many particles pass through the surface) and the regions contained by the surfaces (how many particles are absorbed or cause secondary emission of radiation). Traditional simple-minded meshing partitioning would introduce far too many new (unnecessary) surfaces and volumes. Because computational time is a function of the combinations of surfaces, the resulting increase goes as the number of trimmed surfaces, factorial—even a small increase can double or triple the time required. Larger increases rapidly make computation impossibly slow.
Existing partitioning schemes include octrees (see Yerry, Mark A. and Mark S. Shephard “Automatic Three-Dimensional Mesh Generation By The Modified Octree Technique”, International Journal For Numerical Methods in Engineering, John Wiley, Num 20, pp. 1965-1990, 1984), bounding boxes and bounding polyhedra. The latter two are often referred to as meshing. Octrees are used recursively, utilizing three perpendicular slice planes along the X, Y and Z planes, respectively, that rotely bisect a bounding box around the part to partition a space into eight regions of equal volume. This approach is simple but generally introduces twenty-four new surfaces for each application of partitioning, which runs counter to the stated goal of not introducing complexity. Bounding boxes are also simple and can use geometric information from the object, but are only good for partitioning rectangular regions. Curved or non-boxlike regions will not become simpler under this partitioning scheme. Bounding polyhedra can also be applied similarly, but unless the region to be partitioned contains geometry congruent to the polyhedra, offers no advantage when trying to simplify.